/**
 * Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all
 * elements in arr2 are also in arr1.
 * <p>
 * Sort the elements of arr1 such that the relative ordering of items in arr1 are
 * the same as in arr2. Elements that do not appear in arr2 should be placed at
 * the end of arr1 in ascending order.
 * <p>
 * <p>
 * Example 1:
 * <p>
 * <p>
 * Input: arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
 * Output: [2,2,2,1,4,3,3,9,6,7,19]
 * <p>
 * <p>
 * Example 2:
 * <p>
 * <p>
 * Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
 * Output: [22,28,8,6,17,44]
 * <p>
 * <p>
 * <p>
 * Constraints:
 * <p>
 * <p>
 * 1 <= arr1.length, arr2.length <= 1000
 * 0 <= arr1[i], arr2[i] <= 1000
 * All the elements of arr2 are distinct.
 * Each arr2[i] is in arr1.
 * <p>
 * <p>
 * Related Topics 数组 哈希表 计数排序 排序 👍 242 👎 0
 */


package com.xixi.basicAlgroithms.hash;

public class ID01122RelativeSortArray {
    public static void main(String[] args) {
        Solution solution = new ID01122RelativeSortArray().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int[] relativeSortArray(int[] arr1, int[] arr2) {

            //countting sort, need an array to store the frequency of arr1's elements
            int[] arr1Check = new int[1001];
            for (int j : arr1) {
                arr1Check[j]++;
            }

            //index on inputting arr1
            int i = 0;
            //scan a2 elements, and put in arr1
            for (int a2 : arr2) {
                while (arr1Check[a2] != 0) {
                    arr1[i] = a2;
                    i++;
                    arr1Check[a2]--;
                }
            }

            //scan remaining elements in arr1, put them at the tail
            for (int j = 0; j < arr1Check.length; j++) {
                if (arr1Check[j] > 0) {
                    while (arr1Check[j] != 0) {
                        arr1[i] = j;
                        i++;
                        arr1Check[j]--;
                    }
                }
            }

            return arr1;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}